The present invention relates generally to data processing systems, and more particularly to, predicting multiple branch instructions deep into an instruction flow and performing out of order branch resolution on the multiple branch predictions.
In the integrated circuit (IC) industry, branch instruction prediction is being used to improve the performance of central processing units (CPU). In a software program, branch instructions are used to selectively send instruction execution flow in one of two different directions based upon some criterion (e.g., if A greater than B then goto here else goto there, if X=Y then goto here else goto there, if V bit set then goto here else goto there, etc.). If a processor is forced to wait until the path of the branch is clearly determined before fetching instructions for execution from memory, a xe2x80x9cgapxe2x80x9d in instruction execution flow is experienced within the CPU. It has been found that it is more beneficial to xe2x80x9cpredictxe2x80x9d or xe2x80x9cguessxe2x80x9d which path the branch will eventually traverse and execute instructions down this speculative path before resolution of the exact branch path is determined. If the CPU correctly predicts the branch path more often than not, performance improvements can usually be achieved by removing the execution xe2x80x9cgapsxe2x80x9d from the CPU""s instruction flow (i.e., the CPU is not sitting idle as long).
However, branch instruction prediction is becoming even more complex in modem microprocessors. It is now desired that a processor predict multiple branches deep in the flow of instruction execution and compound speculation on top of speculation. There are significant performance advantages for CPUs that can predict accurately through multiple branch instructions whereby computer instructions that are multiple branch instructions deep are being speculatively executed. However, when predicting through multiple branch instructions, a significant amount of hardware overhead is usually needed in prior art designs. In many cases, the algorithms that control these larger resources inefficiently schedule or assign the resources whereby otherwise available resources are not available for efficient use. In addition, this additional hardware may not be easily scalable to more complex architectures in order to further improve performance in subsequent generations of the microprocessor""s family line. Furthermore, this multiple-branch prediction capability in the architecture may result in difficulty in recovering from a mispredicted branch whereby performance may be adversely impacted if mispredictions occur too frequently.
Therefore, a need exists in the industry for a branch prediction architecture which allows for one or more of branch prediction that progresses multiple branch instructions deep, correction of branch mispredictions in a more efficient manner, reduced hardware overhead associated with the branch architecture, ease of extendibility to more complicated computer architectures to deeper branch prediction, improved allocation of resources, and improved performance.